Shell Sort - O(N^2) - In-place ComparisonΒΆ
It can be seen as either a generalization of sorting by exchange (bubble sort)
or sorting by insertion (insertion sort).
The method starts by sorting pairs of elements far apart from each other,
then progressively reducing the gap between elements to be compared.
Starting with far apart elements _can_ move some out-of-place elements
into position faster than a simple nearest neighbor exchange.
def gap_InsertionSort(L, start, gap):
for i in range(start + gap, len(L), gap):
current_value = L[i]
position = i
while position >= gap and L[position - gap] > current_value:
L[position] = L[position - gap]
position = position - gap
L[position] = current_value
def shellSort(L):
sublist_count = len(L) // 2
while sublist_count > 0:
for start_position in range(sublist_count):
gap_InsertionSort(L, start_position, sublist_count)
print("After increments of size", sublist_count, "The list is", L)
sublist_count = sublist_count // 2
Test:
L = [4, 10, 8, 12, 6, 14, 2, 16, 1]
shellSort(L)
print(L)
Output:
After increments of size 4 The list is [1, 10, 2, 12, 4, 14, 8, 16, 6]
After increments of size 2 The list is [1, 10, 2, 12, 4, 14, 6, 16, 8]
After increments of size 1 The list is [1, 2, 4, 6, 8, 10, 12, 14, 16]
[1, 2, 4, 6, 8, 10, 12, 14, 16]